/*
 * @FilePath: \17_datac:\Users\sxjct\.leetcode\240.搜索二维矩阵-ii.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-30 10:24:19
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-30 10:45:11
 */
/*
 * @lc app=leetcode.cn id=240 lang=cpp
 *
 * [240] 搜索二维矩阵 II
 */

// @lc code=start
class Solution {
public:
    // 逐行 + 二分
    // bool searchMatrix(vector<vector<int>>& matrix, int target) {
    //     int row = matrix.size();        // 行数
    //     int col = matrix[0].size();     // 列数
    //     for(int i = 0; i < row ; i++)
    //     {
    //         int left = 0;
    //         int right = col - 1;
    //         while(left <= right)
    //         {
    //             int mid = (left + right)/2;
    //             if(matrix[i][mid] == target)
    //             {
    //                 return true;
    //             }
    //             else if(matrix[i][mid] < target)
    //             {
    //                 left = mid + 1;
    //             }
    //             else
    //             {
    //                 right = mid - 1;
    //             }
    //         }
    //     }
    //     return false;
    // }

    // 根据对角线确定范围
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        int row = matrix.size();            // 行数
        int col = matrix[0].size();         // 列数
        int i = 0;
        int j = col - 1;
        while(i < row && j >= 0)
        {
            if(matrix[i][j] == target)
            {
                return true;
            }
            else if(matrix[i][j] < target)
            {
                i++;
            }
            else
            {
                j--;
            }

        }
        return false;
        
    }
};
// @lc code=end

